<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>数据结构之栈</title>
  </head>
  <body>
    <script type="text/javascript">
      function Stack() {
        this.dataStore = []; // 保存栈内元素
        this.top = 0; // 标记可以插入新元素的位置，栈内压入元素该变量变大，弹出元素该变量变小
        this.push = push; // 入栈操作
        this.pop = pop; // 出栈操作
        this.peek = peek; // 返回栈顶元素
        this.clear = clear; // 清空栈
        this.length = length; // 栈的长度
        this.isEmpty = isEmpty; // 判断栈是否为空
      }

      // 向栈中压入元素，同时让指针 top+1，一定注意++
      function push(element) {
        this.dataStore[this.top++] = element;
        // this.dataStore.push(element);
      }

      // 出栈操作，同时将 top-1
      function pop() {
        return this.dataStore[--this.top];
        // return this.dataStore.pop();
      }

      // 返回栈顶元素，top-1，返回不删除
      function peek() {
        return this.dataStore[this.top - 1];
        // return this.dataStore[this.dataStore.length - 1];
      }

      // 返回栈内元素个数
      function length() {
        return this.top;
        // return this.dataStore.length;
      }

      // 清空栈
      function clear() {
        this.top = 0;
        // this.dataStore = [];
      }

      // 判断栈是否为空
      function isEmpty() {
        return this.top === 0;
        // return this.dataStore.length === 0;
      }

      // var stack = new Stack();
      // stack.push(1);
      // stack.push(2);
      // console.log('栈的长度：',stack.length());
      // console.log('栈顶元素：', stack.peek());
      // console.log('出栈元素：', stack.pop());
      // console.log('栈顶元素：', stack.peek());

      //判断括号是否合法
      // function is_legal_brackets(string) {
      //   var stack = new Stack();
      //   for (var i = 0; i < string.length; i++) {
      //     var item = string[i];
      //     //遇到左括号，入栈
      //     if (item == "(") {
      //       stack.push(item);
      //       // console.log(stack);
      //     } else if (item == ")") {
      //       //遇到右括号，先判断栈是否为空
      //       if (stack.isEmpty()) {
      //         return false;
      //       } else {
      //         stack.pop(); //弹出左括号
      //       }
      //     }
      //   }
      //   console.log(stack);
      //   //如果栈为空，说明该字符串括号合法
      //   return stack.isEmpty();
      // }
      // console.log(is_legal_brackets('sdf(ds(ew(we)rw)rwqq)qwewe'));
      // console.log(is_legal_brackets('(sd(qwqw)sd(sd))'));
      // console.log(is_legal_brackets('()()sd()(sd()fw))('));

      // function isPalindrome(word) {
      //   var stack = new Stack();
      //   for (var i = 0; i < word.length; i++) {
      //     stack.push(word[i]);
      //   }
      //   var rword = "";
      //   while (stack.length() > 0) {
      //     rword += stack.pop();
      //   }
      //   console.log(rword);
      //   return rword === word;
      // }
      // console.log(isPalindrome('aaddaa'));

      //计算后缀表达式，也称逆波兰表达式
      // function calc_exp(exp) {
      //   var stack = new Stack();
      //   for (var i = 0; i < exp.length; i++) {
      //     var item = exp[i];
      //     if (["+", "-", "*", "/"].indexOf(item) >= 0) {
      //       //从栈顶弹出两个元素
      //       var value1 = stack.pop();
      //       var value2 = stack.pop();
      //       //拼成表达式
      //       var exp_str = value2 + item + value1; //第一次弹出的数放在运算符右边，第二次弹出的数放在运算符左边
      //       //计算并取整
      //       var res = parseInt(eval(exp_str)); //eval() 函数可计算某个字符串，并执行其中的的 JavaScript 代码
      //       //将计算结果压入栈
      //       stack.push(res.toString());
      //     } else {
      //       stack.push(item);
      //     }
      //   }
      //   //若表达式正确，最终栈里应只有一个元素，这就是表达式的值
      //   return stack.pop();
      // }
      // var exp1 = ["4", "13", "5", "/", "+"]; //(4 + (13 / 5)) = 6
      // var exp2 = ['10','6','9','3','+','-11','*','/','*','17','+','5','+'];  // ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
      // console.log(calc_exp(exp1));
      // console.log(calc_exp(exp2));

      // 十进制转二进制
      // function BinaryConversion(number) {
      //   var stack = new Stack();
      //   var remainder;
      //   var binary = ""; // 存储二进制
      //   while (number > 0) {
      //     remainder = number % 2; // 求模取余
      //     stack.push(remainder);
      //     number = Math.floor(number / 2); // 向下取整
      //   }
      //   while (!stack.isEmpty()) {
      //     binary += stack.pop();
      //   }
      //   return binary;
      // }
      // console.log(BinaryConversion(10));

      function StackQueue() {
        var stack1 = new Stack(); //负责添加元素
        var stack2 = new Stack(); //负责删除元素

        this.enqueue = function (item) {
          stack1.push(item);
        };

        this.head = function () {
          if (stack1.isEmpty() && stack2.isEmpty()) {
            return null;
          }
          while (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
              stack2.push(stack1.pop());
            }
          }
          return stack2.peek();
        };

        this.size = function () {
          if (!stack1.isEmpty()) {
            return stack1.length();
          } else {
            if (!stack2.isEmpty()) {
              return stack2.length();
            } else {
              return 0;
            }
          }
        };

        this.dequeue = function () {
          if (stack1.isEmpty() && stack2.isEmpty()) {
            return null;
          }
          while (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
              stack2.push(stack1.pop());
            }
          }
          return stack2.pop();
        };
      }
      var sQueue = new StackQueue();
      sQueue.enqueue(1);
      sQueue.enqueue(2);
      sQueue.enqueue(3);
      console.log(sQueue.head());
      console.log(sQueue.dequeue());
      console.log(sQueue.head());
      console.log(sQueue.size());
      console.log(sQueue.dequeue());
      console.log(sQueue.dequeue());
      console.log(sQueue.size());
    </script>
  </body>
</html>
